M=100;
N=1000;
words=[918,918,918,918,784,918,918,865,2,2,472,230,384,230,865,900,350,786,384,784,900,798,918,655,592,499,821,499,54,213,285,350,655,213,900,377,502,655,213,54,377,466,865,871,80,784,2,472,384,401,13,45,384,317,472,186,317,900,637,78,967,377,608,213,13,784,736,305,590,460,900,78,499,592,317,590,395,967,832,56,798,395,822,309,75,689,689,284,13,104,381,377,230,689,798,262,78,502,281,918,54,682,317,500,978,2,56,56,23,497,472,56,404,384,910,789,871,75,682,711,760,460,722,466,309,933,913,149,655,641,900,395,281,4,786,43,281,78,892,104,46,226,784,158,499,933,608,104,682,592,821,610,588,832,254,757,610,78,255,213,692,675,653,577,299,610,350,506,466,978,78,192,696,608,692,905,726,193,760,78,747,497,282,741,502,403,226,751,371,692,226,963,497,513,168,500,46,592,281,841,758,281,984,251,283,608,963,23,757,989,963,263,285,945,309,248,556,893,466,193,712,299,696,608,75,193,75,751,786,608,662,933,300,760,367,384,41,285,588,871,758,670,822,760,594,458,893,892,527,882,736,637,963,643,670,577,594,168,41,268,749,282,26,89,716,963,248,682,643,584,400,41,592,923,893,711,616,26,168,984,757,513,714,49,0,807,984,367,926,734,749,682,741,192,213,753,653,564,317,751,4,927,594,616,905,52,716,851,564,176,46,268,100,893,421,637,875,497,403,195,474,400,832,875,814,711,38,97,251,758,80,953,49,17,147,236,26,590,421,317,820,6,892,97,923,556,978,201,675,284,421,43,80,809,943,866,38,741,236,466,522,522,218,285,821,299,248,345,937,379,608,695,505,564,927,573,522,300,774,195,953,69,100,643,401,226,875,452,814,458,858,714,226,614,809,409,255,502,377,989,662,851,526,230,609,262,369,146,45,247,78,893,285,268,159,774,505,533,271,892,299,612,869,943,159,0,821,609,655,954,217,67,80,692,548,821,832,655,223,186,121,458,439,446,959,612,230,23,761,80,892,705,477,905,87,52,709,526,161,147,709,901,13,624,573,41,864,183,391,497,522,104,100,505,905,300,678,345,851,161,474,946,309,796,590,409,714,358,893,47,802,704,522,797,798,326,166,493,355,761,564,529,135,371,892,46,170,89,251,459,692,465,274,467,505,943,749,38,80,168,268,405,104,499,778,933,975,987,54,226,444,100,110,573,592,152,96,998,467,870,18,49,285,594,47,166,98,275,612,351,104,786,515,471,567,689,934,75,779,400,126,506,244,961,865,268,716,678,554,654,300,166,567,446,28,438,548,1,798,493,975,262,12,749,402,722,709,768,829,472,854,18,273,551,481,573,158,893,147,493,589,51,920,657,236,796,299,608,104,159,12,715,805,575,333,802,587,987,829,150,389,887,371,151,887,954,733,329,741,751,38,774,798,356,146,832,223,548,589,747,375,760,751,892,741,592,529,394,638,527,670,21,232,580,967,809,78,954,0,78,367,282,836,193,760,353,961,300,954,736,655,198,556,381,21,348,809,831,963,391,436,567,572,379,54,953,186,572,789,864,655,67,159,579,501,898,869,442,127,56,947,805,343,405,52,709,564,262,461,821,251,0,814,527,300,74,933,98,653,324,373,954,702,735,798,126,74,901,395,408,147,821,756,615,621,579,205,466,206,273,364,8,47,244,853,717,549,873,335,438,615,751,875,476,38,989,377,268,137,809,458,186,30,186,369,865,210,264,928,802,80,147,26,195,160,872,527,461,734,393,38,538,255,475,829,30,186,458,533,586,508,893,305,502,62,476,108,707,213,76,832,554,349,409,945,734,598,156,400,953,742,864,892,868,685,98,615,226,487,607,16,610,404,633,954,16,221,760,811,67,118,801,900,127,529,718,367,569,778,218,89,384,972,452,400,723,255,60,492,652,384,613,348,548,395,309,923,473,26,121,851,168,947,62,153,947,2,49,807,749,147,784,213,371,695,716,641,403,763,275,275,305,461,459,206,430,928,682,253,734,685,66,751,28,203,377,933,481,379,490,658,765,183,313,609,919,98,588,589,821,420,925,615,363,608,430,616,776,392,507,16,658,255,211,705,797,975,231,275,889,333,299,895,218,390,217,889,726,787,961,497,592,987,566,76,420,227,80,418,535,578,403,820,150,658,255,103,689,836,505,367,685,821,392,643,201,76,832,567,613,285,810,150,741,144,458,576,841,638,919,875,711,436,557,891,217,26,292,250,108,166,41,305,998,941,199,847,46,371,273];